//You are given an n x n 2D matrix representing an image, rotate the image by 90
// degrees (clockwise). 
//
// You have to rotate the image in-place, which means you have to modify the inp
//ut 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. 
//
// 
// Example 1: 
//
// 
//Input: matrix = [[1,2,3],  3 2 1
//                 [4,5,6],  6 5 4
//                [7,8,9]]   9 8 7
//Output: [      [7,4,1],
//               [8,5,2],
//               [9,6,3]]
// 
//
// Example 2: 
//
// 
//Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
//Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
// 
//
// Example 3: 
//
// 
//Input: matrix = [[1]]
//Output: [[1]]
// 
//
// Example 4: 
//
// 
//Input: matrix = [[1,2],[3,4]]
//Output: [[3,1],[4,2]]
// 
//
// 
// Constraints: 
//
// 
// matrix.length == n 
// matrix[i].length == n 
// 1 <= n <= 20 
// -1000 <= matrix[i][j] <= 1000 
// 
// Related Topics 数组 
// 👍 879 👎 0


package leetcode.editor.cn;

//Java：Rotate Image
class P48RotateImage {
    public static void main(String[] args) {
        Solution solution = new P48RotateImage().new Solution();
        // TO TEST
        solution.rotate(new int[][]{
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}});

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void rotate(int[][] matrix) {
            //横向交换
            for (int i = 0; i < matrix.length; i++) {
                int[] arr = matrix[i];
                int left = 0, right = arr.length - 1;
                while (left <= right) {
                    int temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                    left++;
                    right--;
                }
            }
            //斜向交换
            int bottomX = matrix.length - 1;
            int topY = matrix[0].length - 1;

            for (int i = bottomX - 1, j = 0; i >= 0 && j <= topY; ) {
                int nextRow = i;
                int nextCol = j;
                while (nextRow < bottomX && nextCol < topY) {
                    nextRow++;
                    nextCol++;
                }
                int startLeft = i;
                int startRight = j;
                while (startLeft < nextRow && startRight < nextCol) {
                    int temp = matrix[startLeft][startRight];
                    matrix[startLeft][startRight] = matrix[nextRow][nextCol];
                    matrix[nextRow][nextCol] = temp;
                    startLeft++;
                    startRight++;
                    nextRow--;
                    nextCol--;
                }
                int m = i == 0 ? j++ : i--;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}